"""4.寻找两个正序数组的中位数"""
from typing import List


class Solution4:

    def __init__(self):
        pass

    """方法1：先合并，再取中位数"""

    def findMedianSortedArrays1(self, nums1: List[int], nums2: List[int]) -> float:
        i = 0
        j = 0
        list1 = list()
        while i < len(nums1) or j < len(nums2):
            if j == len(nums2):
                list1.append(nums1[i])
                i += 1
            elif i == len(nums1):
                list1.append(nums2[j])
                j += 1
            elif nums1[i] < nums2[j]:
                list1.append(nums1[i])
                i += 1
            else:
                list1.append(nums2[j])
                j += 1
        if len(list1) % 2 == 0:
            return (list1[int(len(list1) / 2) - 1] + list1[int(len(list1) / 2)]) / 2
        else:
            return list1[int(len(list1) / 2)]

    """方法2，二分查找法"""
    def findMedianSortedArrays2(self, nums1: List[int], nums2: List[int]) -> float:
        m = len(nums1)
        n = len(nums2)

        if (m + n) % 2 == 0:
            left = self.get_kvalue(nums1, nums2, int(((m + n) / 2)))
            right = self.get_kvalue(nums1, nums2, int(((m + n) / 2)) + 1)
            return (left + right) / 2
        else:
            return self.get_kvalue(nums1, nums2, int(((m + n) / 2)) + 1)

    """获取两个数组中第k小的数"""
    def get_kvalue(self, nums1, nums2, k):
        m = len(nums1)
        n = len(nums2)

        # 调换位置
        if m > n:
            return self.get_kvalue(nums2, nums1, k)
        # 退出条件1：如果短的长度为0，则第k小的数肯定在长的数组中
        if m == 0:
            return nums2[k - 1]
        # 退出条件2：第k小的数在两个数组当前位置的最短处
        if k == 1:
            return min(nums1[0], nums2[0])

        i = min(m, int(k/2)) - 1
        j = min(n, int(k/2)) - 1

        if nums1[i] > nums2[j]:

            return self.get_kvalue(nums1, nums2[j+1::], k - j - 1)
        else:
            return self.get_kvalue(nums1[i+1::], nums2, k - i - 1)




if __name__ == '__main__':
    sl = Solution4()
    print(sl.findMedianSortedArrays2([1, 2], [3, 4]))
    list1 = [1, 2, 3]
    list2 = list1[1::]
    print(list1)
    print(list2)